package mashibing.class14;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-05-31
 */
public class Class14_4_IPO {

    // 最多K个项目
    // W是初始资金
    // Profits[] Capital[] 一定等长
    // 返回最终最大的资金
    public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
        // 成本排序
        PriorityQueue<Program> capitalQueue = new PriorityQueue<>(new CapitalComparator());
        // 利润排序
        PriorityQueue<Program> profitQueue = new PriorityQueue<>(new ProfitComparator());
        for (int i = 0; i < Profits.length; i++) {
            capitalQueue.add(new Program(Profits[i],Capital[i]));
        }
        for (int i = 0; i < K; i++) {
            while (!capitalQueue.isEmpty() && capitalQueue.peek().c <= W) {
                profitQueue.add(capitalQueue.poll());
            }
            if(profitQueue.isEmpty()) {
                return W;
            }
            W += profitQueue.poll().p;
        }
        return W;
    }

    public static class Program {
        public int p;
        public int c;

        public Program(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    public static class CapitalComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.c - o2.c;
        }
    }

    public static class ProfitComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o2.p - o1.p;
        }
    }
}
